import java.util.*;

public class Text3 {
    public List<String> topKFrequent(String[] words, int k) {
        //1、先统计单词出现的次数->存储到了map当中
        Map<String,Integer> map = new HashMap<>();
        for(String word : words) {
            if(map.get(word) == null) {
                map.put(word,1);
            }else {
                int val = map.get(word);
                map.put(word,val+1);
            }
        }
        //2、遍历好统计好的Map，把每组数据存储到小根堆当中
        PriorityQueue<Map.Entry<String,Integer>> minHeap =
                new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        //放元素的时候 如果频率相同 我们转变为大根堆-》按照单词的字典序
                        if(o1.getValue().compareTo(o2.getValue()) == 0) {
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });

        for(Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                //你要找最大的频率的单词
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {
                    //def->2                     abc-> 2
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        List<String> ret = new ArrayList<>();
        //放到了小根堆 2   3    4
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        // 2  3   4 ->  4 3 2
        Collections.reverse(ret);
        return ret;
    }
}
